package com.leetcode.array;

import java.util.Arrays;

/**
 * @author: ZhouBert
 * @date: 2019/10/14
 * @description: 16. 最接近的三数之和
 * B
 * 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
 * <p>
 * 例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
 * <p>
 * 与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/3sum-closest
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ThreeSumClosest16 {

	/**
	 * 1.排序；
	 * 2.
	 *
	 * @param nums
	 * @param target
	 * @return
	 */
	public static int threeSumClosest(int[] nums, int target) {
		///1.排序
		Arrays.sort(nums);

		///既然必有唯一解，先用前三个元素进行作为 min
		int closestNum = nums[0] + nums[1] + nums[2];

		///2.双指针写法(双指针就没必要二分法了)
		///todo:感觉一直沉浸思维也不够灵活了。先想明白什么算法步骤能解决这个问题，then do it
		///左指针，右指针
		int left, right;
		for (int i = 0; i < nums.length - 2; i++) {
			left = i + 1;
			///确定右坐标 v1.直接取最后一个元素
			right = nums.length - 1;

			while (left < right) {
				int curNum = nums[i] + nums[left] + nums[right];

				if (Math.abs(curNum - target) < Math.abs(closestNum - target)) {
					closestNum = curNum;
				}
				if (curNum < target) {
					left++;
					///left+=(right-left)/2==0?1:(right-left)/2;
				} else if (curNum > target) {
					right--;
					///right-=(right-left)/2==0?1:(right-left)/2;
				} else {
					return target;
				}
			}

		}
		return closestNum;

	}


	/**
	 * 确定右指针所在索引(好吧，双指针的话感觉不好用二分了)
	 *
	 * @param target
	 * @param nums
	 * @param i1
	 * @return
	 */
	public int[] getRightIndex(int target, int[] nums, int i1) {
		int[] ans = new int[2];
		///如果最大的数都小于target，那么只需要判断最大的情况
		if (nums[i1] + nums[nums.length - 1] + nums[nums.length - 2] < target) {
			ans[0]=nums.length - 2;
			ans[1]=nums.length - 1;
		} else if (nums[i1] + nums[i1+1] + nums[i1+2] > target){
			ans[0]=i1+1;
			ans[1]=i1+2;
		}else {
			return null;
		}
		return ans;
	}

	public static void main(String[] args) {
		int[] num = new int[]{-1, 2, 1, -4};
		num = new int[]{1, 2, 4, 8, 16, 32, 64, 128};
		int target = 1;
		target = 82;
		threeSumClosest(num, target);
	}
}
